package main

import (
	"fmt"
)

//dp:4ms 98%,4.2MB 16%
func maxValue(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			dp[i][j] = grid[i-1][j-1] + max(dp[i-1][j], dp[i][j-1])
		}
	}
	return dp[m][n]
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

//dp1:4ms 98%, 4.8MB 5%
func maxValue1(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	dp := [][]int{{grid[0][0]}}
	for i := 1; i < m; i++ {
		dp = append(dp, []int{grid[i][0] + dp[i-1][0]})
	}
	for i := 1; i < n; i++ {
		dp[0] = append(dp[0], grid[0][i]+dp[0][i-1])
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i] = append(dp[i], grid[i][j]+max(dp[i-1][j], dp[i][j-1]))
		}
	}
	return dp[m-1][n-1]
}

func main() {
	fmt.Println(maxValue([][]int{{1}}))
	dp := make([][]int, 4)
	fmt.Println(dp)
	fmt.Println(maxValue1([][]int{{1}}))
}
